package merisis.experiments.gcs;

import static java.lang.Math.log;
import static java.lang.String.format;

import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;

import junit.framework.Assert;

import org.junit.Ignore;
import org.junit.Test;

public class GuessComplementSearchExperiment {

	@Test
	@Ignore
	public void doExperiment1() {

		GCSEInstrument.DEBUG = false;

		doUniformCase();
		doPolynomial();
	}

	@Test
	public void doExperiment2() throws IOException {

		GCSEInstrument.DEBUG = false;

		FileWriter w = new FileWriter("polynomial-2.txt");
		w.append(String.format("access_cnt\n"));

		int sizeOfArray = 1 << 15;
		int scale = (int) (log(sizeOfArray) / Math.log(2)) + 1;

		GCSEInstrument[] insts = new GCSEInstrument[5];
		for (int i = insts.length - 1; i >= 0; i--) {
			insts[i] = new GCSEInstrument("group-" + i, scale);
		}

		System.out.println("** POLYNOMIAL **");
		System.out.println(format("size=%d, scale=%d", sizeOfArray, scale));

		long[] data = ExperimentUtil.genPolynomial2(2, sizeOfArray);
		// print(a);

		AbstractGuessComplemetSearch[] algorithms;
		algorithms = new AbstractGuessComplemetSearch[] { new GCSearch7() };

		for (int i = 0; i < data.length; i++) {

			long key = data[i];
			for (int j = 0; j < algorithms.length; j++) {

				AbstractGuessComplemetSearch s = algorithms[j];

				s.setData(data);
				long position = s.search(0, data.length - 1, key);
				insts[j].merge(s.instrument);
				if (position < 0 || key != s.access(position)) {
					GCSEInstrument.DEBUG = true;
					s.setData(data);

					System.out.println("-------------------- key=" + key);

					s.search(0, data.length - 1, key);

					Assert.fail(String.format("algorithm(%d), pos=%d", j, key));
				}
				w.append(String.format("%d\n", s.instrument.getAccessCount()));

				// if (s.instrument.getAccessCount() > 25) {
				//
				// s.setData(data);
				// System.out.println("-------------------- key=" + key);
				//
				// GCSEInstrument.DEBUG = true;
				// s.instrument = new GCSEInstrument("xxx", s.instrument
				// .getScale());
				// s.search(0, data.length - 1, key);
				// throw new IllegalStateException();
				// }

			}
		}

		for (int i = 0; i < insts.length; i++) {
			insts[i].print();
		}
	}

	void doUniformCase() {

		Random rand = new Random();

		int sizeOfArray = 46339 * 8;
		int scale = (int) (log(sizeOfArray) / Math.log(2)) + 1;

		GCSEInstrument[] insts = new GCSEInstrument[5];
		for (int i = insts.length - 1; i >= 0; i--) {
			insts[i] = new GCSEInstrument("group-" + i, scale);
		}

		System.out.println("** UNIFORM **");
		System.out.println(format("size=%d, scale=%d", sizeOfArray, scale));

		for (int i = 0; i < 10; i++) {

			long[] a = ExperimentUtil.genRandArray(0, 100000, sizeOfArray);
			for (int j = 0; j < 100; j++) {

				long key = a[rand.nextInt(sizeOfArray)];
				testBody(insts, a, key);
			}
		}

		for (int i = 0; i < insts.length; i++) {
			insts[i].print();
		}
	}

	void doPolynomial() {

		int sizeOfArray = 8 * (((int) Math.sqrt(Integer.MAX_VALUE)) - 1);
		int scale = (int) (log(sizeOfArray) / Math.log(2)) + 1;

		GCSEInstrument[] insts = new GCSEInstrument[5];
		for (int i = insts.length - 1; i >= 0; i--) {
			insts[i] = new GCSEInstrument("group-" + i, scale);
		}

		System.out.println("** POLYNOMIAL **");
		System.out.println(format("size=%d, scale=%d", sizeOfArray, scale));

		long[] a = ExperimentUtil.genPolynomial2(2, sizeOfArray);
		// print(a);

		for (int i = 1; i < 1000; i++) {

			long key = a[(new Random()).nextInt(sizeOfArray)];

			testBody(insts, a, key);
		}

		for (int i = 0; i < insts.length; i++) {
			insts[i].print();
		}
	}

	public void testBody(GCSEInstrument[] insts, long[] data, long key) {

		AbstractGuessComplemetSearch[] algorithms = new AbstractGuessComplemetSearch[] {
				new GCSearch0(), new GCSearch5(), new GCSearch6(),
				new GCSearch7() };

		for (int i = 0; i < algorithms.length; i++) {
			algorithms[i].setData(data);
		}

		for (int i = 0; i < algorithms.length; i++) {

			AbstractGuessComplemetSearch s = algorithms[i];

			long position = s.search(0, data.length - 1, key);
			insts[i].merge(s.instrument);
			if (position < 0 || key != s.access(position)) {
				GCSEInstrument.DEBUG = true;
				s.setData(data);
				System.out.println("-------------------- key=" + key);

				s.search(0, data.length - 1, key);

				Assert.fail(String.format("algorithm(%d), pos=%d", i, key));
			}

			if (s.instrument.getAccessCount() > 25) {

				s.setData(data);
				System.out.println("-------------------- key=" + key);

				GCSEInstrument.DEBUG = true;
				s.instrument = new GCSEInstrument("xxx", s.instrument
						.getScale());
				s.search(0, data.length - 1, key);
				throw new IllegalStateException();
			}

		}
	}

	public int gradsearch(int[] array, int start, int end, int key,
			GCSEInstrument ins) {

		int low = start;
		int high = end;

		int bottomVal = access(array, low, ins);
		int topVal = access(array, high, ins);

		while (low <= high) {

			ins.rountcount++;

			// jumping function
			int jump;
			int didx = high - low;
			int step;
			step = computeStep(key, low, bottomVal, high, topVal, ins);
			jump = step + low;
			if (low == jump) {
				// diffcult to jump, so climb up carefully
				jump = low + 1;
			}

			int jumpVal = access(array, jump, ins);

			if (jumpVal < key) {
				low = jump;
				bottomVal = jumpVal;
			} else if (jumpVal > key) {
				if (high == jump) {
					return -low;
				}
				high = jump;
				topVal = jumpVal;

			} else
				return jump; // key found
		}

		return -(low + 1); // key not found.
	}

	public int gradsearch1(int[] array, int start, int end, int key,
			GCSEInstrument ins) {

		int low = start;
		int high = end;

		int bottomVal = access(array, low, ins);
		int topVal = access(array, high, ins);

		while (low <= high) {
			ins.rountcount++;

			if (high < low)
				throw new IllegalStateException("negtive");

			// jumping function
			int jump;
			int didx = high - low;
			int step;
			step = computeStep(key, low, bottomVal, high, topVal, ins);

			if (step < 2) {
				if (didx > 2) {
					step = 2;
					// System.out.println("blind jump");
				} else {
					// diffcult to jump, so climb up carefully
					step = 1;
				}
			}

			jump = step + low;

			int jumpVal = access(array, jump, ins);

			if (jumpVal < key) {
				low = jump;
				bottomVal = jumpVal;
			} else if (jumpVal > key) {
				if (high == jump) {
					return -low;
				}
				high = jump;
				topVal = jumpVal;

			} else
				return jump; // key found
		}

		return -(low + 1); // key not found.
	}

	public int gradsearch2(int[] array, int start, int end, int key,
			GCSEInstrument ins) {

		int low = start;
		int high = end;

		int bottomVal = access(array, low, ins);
		int topVal = access(array, high, ins);

		int step0 = 0;

		while (low <= high) {
			ins.rountcount++;

			if (high < low)
				throw new IllegalStateException("negtive");

			// jumping function
			int jump;

			int didx = high - low;
			int step;
			step = computeStep(key, low, bottomVal, high, topVal, ins);

			if (step0 == step && didx > 2) {

				// blind jump
				jump = (low + high) >> 1;
				// System.out.println("blind!");
			} else {
				if (step == 0) {
					// diffcult to jump, so climb up carefully
					step = 1;
					jump = step + low;
				} else {
					jump = step + low;
				}
			}

			step0 = step;

			int jumpVal = access(array, jump, ins);

			if (jumpVal < key) {
				low = jump;
				bottomVal = jumpVal;
			} else if (jumpVal > key) {
				if (high == jump) {
					return -low;
				}
				high = jump;
				topVal = jumpVal;

			} else
				return jump; // key found
		}

		return -(low + 1); // key not found.
	}

	public int access(int[] a, int idx, GCSEInstrument ins) {

		ins.doAccess();
		return a[idx];
	}

	public int computeStep(int key, int low, int bottomVal, int high,
			int topVal, GCSEInstrument inst) {

		int dval = key - bottomVal;
		int didx = high - low;
		int scope = topVal - bottomVal;
		int step;

		step = (int) ((((double) dval) * didx) / scope);

		// int stepint;
		// if (dval > didx) {
		// stepint = (dval / scope) * didx;
		// } else {
		// stepint = (didx / scope) * dval;
		// }
		// stepint = (int) ((((long) dval) * didx) / (long) scope);
		//
		// inst.stepdiff += Math.abs(step - stepint);

		if (step < 0)
			throw new IllegalStateException("<0, " + step);

		// System.out.println(String.format(
		// "l<%d(%d)>, h<%d(%d)>, m<%d(%d, step=%d)>, k=%d",
		// bottomVal, low, topVal, high, jumpVal, jump, step, scope
		// / didx));

		return step;
	}
}
